typedef int KeyType;
typedef struct TRNode{
	KeyType key;
	int priority;
}TRNode, *Treap;
int RandPriority(){
	return rand();
}
void RightRotate(Treap &T){
	Treap p = T->lchild;
	T->lchild = p->rchild; p->rchild = T;
	p = T;
}
void LeftRotate(Treap &T){
	Treap p = T->rchild;
	T->rchild = p->lchild; p->lchild = T;
	p = T;
}
Treap SearchTreap(Treap T, KeyType key){
	Treap p = T;
	while (p && p->key != key){
		if (p->key > key){
			if (p->lchild){
				p = p->lchild;
			}
			else break;
		}
		else {
			if (p->rchild){
				p = p->rchild;
			}
			else break;
		}
	}
	return p;
}
void InsertTreap(Treap T, KeyType key){
	if (!T){
		T = (Treap)malloc(sizeof(TRNode));
		T->key = key; T->priority = RandPriority();
		T->lchild = T->rchild = NULL;
	}
	else {
		if (T->key > key){
			InsertTreap(T->lchild, key);
			if (T->lchild->priority < T->priority){
				RightRotate(T);
			}
		}
		else if (T->key < key){
			InsertTreap(T->rchild, key);
			if (T->rchild->priority < T->priority){
				LeftRotate(T);
			}
		}
		else return;
	}
}
void DeleteTreap_One(Treap &T, KeyType key){
	if (!T) return;
	if (T->key == key){
		if (!T->rchild && !T->lchild){
			free(T); T = NULL;
		}
		else if (!T->rchild){
			Treap p = T->lchild; free(T); T = p;
		}
		else if (!T->lchild){
			Treap p = T->rchild; free(T); T = p;
		}
		else {
			Treap pred = T, p = T->rchild;
			while (p->lchild){
				pred = p; p = p->lchild;
			}
			if (pred->lchild == p){
				pred->lchild = p->rchild;
			}
			else pred->rchild = p->rchild;
			T->key = p->key; free(p);
		}
	}
	else if (T->key > key){
		DeleteTreap_One(T->lchild, key);
	}
	else DeleteTreap_One(T->rchild, key);
}

void DeleteTreap_Two(Treap T, KeyType key){
	Treap p = SearchTreap(T, key);
	if (p && p->key == key){
		Treap pred = NULL;
		while (1){
			if (p->lchild && p->rchild){
				if (p->lchild->priority > p->rchild->priority){
					LeftRotate(p); p = p->lchild;
				}
				else {
					RightRotate(p); p = p->rchild;
				}
			}
			else if (p->lchild){
				RightRotate(p); pred = p; p = p->rchild;
			}
			else if (p->rchild){
				LeftRotate(p); pred = p; p = p->lchild;
			}
			else break;
		}
		if (pred->lchild == p){
			pred->lchild = NULL; free(p);
		}
		else {
			pred->rchild = NULL; free(p);
		}
	}
}
Treap FindMaxTreap(Treap T){
	Treap p = T;
	while (p->rchild){
		p = p->rchild;
	}
	return p;
}
Treap FindMinTreap(Treap T){
	Treap p = T;
	while (p->lchild){
		p = p->lchild;
	}
	return p;
}
void SplitTreap(Treap &T, Treap &S1, Treap &S2, KeyType key){
	Split(T, key);
	S1 = T->lchild; S2 = T->rchild;
	free(T); T = NULL;
}
void Split(Treap &T, KeyType key){
	if (!T){
		T = (Treap)malloc(sizeof(TRNode));
		T->key = key; T->priority = -1;
		T->lchild = T->rchild = NULL;
	}
	else {
		if (T->key > key){
			Split(T->lchild, key);
			RightRotate(T);
		}
		else {
			Split(T->rchild, key);
			LeftRotate(T);
		}
	}
}
void MergeTreap(Treap &T, Treap S1, Treap S2){
	if (!S1 && !S2){
		T = NULL; return;
	}
	else if (!S1){
		T = S2; return;
	}
	else if (!S2){
		T = S1; return;
	}
	Treap p = (Treap)malloc(sizeof(TRNode));
	p->key = (FindMaxTreap(S1) + FindMinTreap(S2)) / 2;
	p->priority = MAX_INT;
	p->lchild = S1; p->rchild = S2;
	T = S1->key > S2->key ? S2 : S1;
	while (1){
		if (p->lchild && p->rchild){
			if (p->lchild->key > p->rchild->key){
				LeftRotate(p); p = p->lchild;
			}
			else {
				RightRotate(p); p = p->rchild;
			}
		}
		else if (!p->lchild){
			RightRotate(p); break;
		}
		else if (!p->rchild){
			LeftRotate(p); break;
		}
	}
	if (p->lchild->priority == MAX_INT){
		free(p->lchild); p->lchild = NULL;
	}
	else {
		free(p->rchild); p->rchild = NULL;
	}
}